/*
 * @lc app=leetcode.cn id=115 lang=java
 *
 * [115] 不同的子序列
 */

// @lc code=start
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];
        // dp[i][j]表示为s[0~i] 和t[0~j]均闭区间的子序列个数
        
        for (int i = 0; i <= m; i++)//t串长为0，为空串的时候，S的子序列中t只出现一次。。
            dp[i][0] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (j > i)//t序列长于s序列是不可能有解的，所以直接跳过。
                    continue;
                if (s.charAt(i - 1) == t.charAt(j - 1)) {//从1开始数，这里是映射的第i个字符。
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    // 啊，我懂了。
                } else {
                    dp[i][j] = dp[i - 1][j];
                    // 这部分我理解，如果s与j串末尾的字符不一样，那么显然s的最后一个字符是用不上的。
                }
            }
        }
        return dp[m][n];
    }
}
// @lc code=end

